#include "stdafx.h"
#include "BinQuery.h"

#include <iostream>

using namespace std;

#define VECTOR_INIT_CAPACITY 16

BinQuery::BinQuery(unsigned int dimension, double* coord_max, double* coord_min, unsigned int division_depth, unsigned int* division)
	:PointSet(dimension, coord_max, coord_min)
{
	this->division_depth = division_depth;
	this->division = new unsigned int[division_depth];
	for (unsigned int i = 0; i < division_depth; ++i)
	{
		this->division[i] = division[i];
	}

	validation_initialization();

	root = new Bin();
	root->key_level = 0;
	root->count = 0;
	root->key_min = new double[dimension];
	root->key_max = new double[dimension];
	for (unsigned int i_dim = 0; i_dim < dimension; ++i_dim)
	{
		root->key_min[i_dim] = coord_min[i_dim];
		root->key_max[i_dim] = coord_max[i_dim];
	}

	n_bins = 1;

	construct_bin_structure(root);
}

BinQuery::~BinQuery()
{
	delete[] division;
	division = NULL;
	delete root;
	root = NULL;
}

void BinQuery::validation_initialization()
{
	if (division_depth < dimension)
		throw new std::exception("EXCEPTION: division_depth must be equals to or larger than dimension");
	for (unsigned int i = 0; i < division_depth; ++i)
		if (division[i] <= 0)
			throw std::exception("EXCEPTION: division in each dimension must be positive");
}

void BinQuery::construct_bin_structure(Bin* bin)
{
	bin->key_dimension = this->dimension;
	if (bin->key_level < this->division_depth)
	{
		bin->keys = NULL;
		bin->objects = NULL;

		unsigned int cur_index = bin->key_level;
		while (cur_index >= dimension)
			cur_index -= dimension;

		unsigned int n_branch = division[cur_index];
		bin->sections = new vector<Bin*>(n_branch);

		double range_level = bin->key_max[cur_index] - bin->key_min[cur_index];
		double delta_level = range_level / n_branch;
		bin->key_delta = delta_level;

		for (unsigned int i = 0; i < n_branch; ++i)
		{
			Bin* b_i = new Bin();
			n_bins++;
			bin->sections->at(i) = b_i;

			b_i->key_level = bin->key_level + 1;

			b_i->key_min = new double[dimension];
			b_i->key_max = new double[dimension];
			for (unsigned int i_dim = 0; i_dim < dimension; ++i_dim)
			{
				b_i->key_min[i_dim] = bin->key_min[i_dim];
				b_i->key_max[i_dim] = bin->key_max[i_dim];
			}
			b_i->key_min[cur_index] = bin->key_min[cur_index] + i * delta_level;
			b_i->key_max[cur_index] = b_i->key_min[cur_index] + delta_level;

			construct_bin_structure(b_i);
		}
	}
	else
	{
		bin->sections = NULL;
		
		bin->keys = new vector<double*>(VECTOR_INIT_CAPACITY);
		bin->keys->clear();	// init the array with positive capacity
		bin->objects = new vector<void*>(VECTOR_INIT_CAPACITY);
		bin->objects->clear();	// init the array with positive capacity
	}
}

void BinQuery::add_point(double* key, void* object)
{
	if (key == NULL)
		throw new exception("EXCETION: The given key of the point is NULL");
	if (root == NULL)
		throw new exception("EXCEPTION: Forget to call construct_bin_structure?");

	if (inSpace(key))
		root->add_point(key, object);
}

void BinQuery::nearest_neighbor(double* key, double range, std::vector<double*>*& coords, std::vector<void*>*& results)
{
	if (range <= 0)
		throw new exception("EXCEPTION: Range must be positive");

	if (coords == NULL)
		coords = new vector<double*>(VECTOR_INIT_CAPACITY);
	if (results == NULL)
		results = new vector<void*>(VECTOR_INIT_CAPACITY);

	coords->clear();
	results->clear();

	if (inSpace(key) == false)
		return;

	root->range_exclusive_traversal(key, range, coords, results);
}

BinQuery::Bin::Bin()
{
	key_level = 0;
	key_delta = 0;
	key_min = NULL;
	key_max = NULL;
	count = 0;
	sections = NULL;
	keys = NULL;
	objects = NULL;
}

BinQuery::Bin::~Bin()
{
	delete[] key_min;
	key_min = NULL;
	delete[] key_max;
	key_max = NULL;
	delete keys;
	keys = NULL;
	delete objects;
	objects = NULL;
	if (sections != NULL)
	{
		unsigned int n_sections = sections->size();
		for (unsigned int i = 0; i < n_sections; ++i)
			delete sections->at(i);
		delete sections;
		sections = NULL;
	}
}

void BinQuery::Bin::add_point(double* key, void* object)
{
	if (sections != NULL)
	{
		int key_index = this->key_level;
		while (key_index >= key_dimension)
			key_index -= key_dimension;

		unsigned int rasterization = (key[key_index] - key_min[key_index]) / key_delta;
		Bin* sub_bin = sections->at(rasterization);
		sub_bin->add_point(key, object);
	}
	else
	{
		keys->push_back(key);
		objects->push_back(object);
	}
	count++;
}

void BinQuery::Bin::range_exclusive_traversal(double* key, double range, vector<double*>*& coords, vector<void*>*& objects)
{
	if (count <= 0) return;
	
	if (sections == NULL)
	{
		double r2 = range * range;
		for (unsigned int i = 0; i < this->keys->size(); ++i)
		{
			double* key_i = this->keys->at(i);
			double dist2 = Euclidean2(key_dimension, key, key_i);
			if (dist2 <= r2)
			{
				coords->push_back(key_i);
				objects->push_back(this->objects->at(i));
			}
		}
	}
	else
	{
		unsigned int key_index = key_level;
		while (key_index >= key_dimension)
			key_index -= key_dimension;

		double b_i_min = key_min[key_index];
		double b_i_max = b_i_min + key_delta;
		double range_min = key[key_index] - range;
		double range_max = key[key_index] + range;

		for (unsigned int i = 0; i < sections->size(); ++i)
		{
			if (b_i_max > range_min && b_i_min < range_max)
				sections->at(i)->range_exclusive_traversal(key, range, coords, objects);

			b_i_min = b_i_max;
			b_i_max += key_delta;
		}
	}
}